#define _CRT_SECURE_NO_WARNINGS 1

//
//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    int* arr = (int*)malloc(sizeof(int) * numsSize);
//    int left = 1;
//    int right = 1;
//    for (int i = 0; i < numsSize; ++i)
//    {
//        arr[i] = left;
//        left *= nums[i];
//    }
//    for (int i = numsSize - 1; i >= 0; --i)
//    {
//        arr[i] *= right;
//        right *= nums[i];
//    }
//    *returnSize = numsSize;
//    return arr;
//}

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[0] = g[n - 1] = 1;
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; --i) g[i] = g[i + 1] * nums[i + 1];
        vector<int> ret(n);
        for (int i = 0; i < n; ++i)
        {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};